package com.搜索和回溯;

class Solution4 {
    public boolean exist(char[][] board, String word) {
        //将字符串转变为字符数组
        char[] words = word.toCharArray();
//        遍历字符串
        for(int i=0;i<board.length;i++){
            for (int j = 0; j < board[0].length; j++) {
                if(dfs(board,words,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }
    boolean dfs(char[][] board,char[] words,int i,int j,int k){
        //终止条件
        if(i<0||i>=board.length||j<0||j>board[0].length||board[i][j]!=words[k]) return false;
        if(k==words.length-1) return true;
        //递推
        board[i][j]='\0';//将当前元素设置为空字符串（Python: '' , Java/C++: '\0'），防止重复访问
        //递归当前元素的四个方向，下上右左，匹配下一个元素
        boolean res=dfs(board,words,i+1,j,k+1)||dfs(board,words,i-1,j,k+1)||
                dfs(board,words,i,j+1,k+1)||dfs(board,words,i,j-1,k+1);//有一个ture则整体为true
        //将矩阵元素还原
        board[i][j]=words[k];//因为上面有判断board[i][j]!=words[k]，它不成立，则board[i][j]=words[k]，所有这需要这样，就可以将矩阵还原。
        return res;
    }
}
public class 剑指Offer12矩阵中的路径 {
    public static void main(String[] args) {

    }
}
